package com.duoduo.树;

import com.duoduo.TreeNode;

import java.util.*;

/**
 * @program: algorithm
 * @description: 二叉树的锯齿形层序遍历103
 * 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[20,9],[15,7]]
 * @author: chaidl  ！
 * @create: 2022-05-21 22:50
 */
public class 二叉树的锯齿形层序遍历103 {
	//迭代 广度优先遍历
	public List<List<Integer>> zigzagLevelOrder1(TreeNode root) {
		//定义返回结果
		List<List<Integer>> ans = new LinkedList<List<Integer>>();
		if (root == null) {
			return ans;
		}
		Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();
		//根节点压入队列
		nodeQueue.offer(root);
		//判断是否从左边开始
		boolean isOrderLeft = true;
		//如果队列不为空
		while (!nodeQueue.isEmpty()) {
			Deque<Integer> levelList = new LinkedList<Integer>();
			//得到栈的数据大小
			int size = nodeQueue.size();
			for (int i = 0; i < size; ++i) {
				//出栈
				TreeNode curNode = nodeQueue.poll();
				//如果从左往右，就将当前数据放入最后一个
				if (isOrderLeft) {
					levelList.offerLast(curNode.val);
				} else {
					//如果从右往左，就将当前数据放入第一个
					levelList.offerFirst(curNode.val);
				}
				if (curNode.left != null) {
					nodeQueue.offer(curNode.left);
				}
				if (curNode.right != null) {
					nodeQueue.offer(curNode.right);
				}
			}
			ans.add(new LinkedList<Integer>(levelList));
			isOrderLeft = !isOrderLeft;
		}
		return ans;
	}
	public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> result = new ArrayList<>();
		travel(result,root,0);
		return  result;
	}
	
	private void travel(List<List<Integer>> result, TreeNode root, int height) {
		if (root == null){
			return;
		}
		if (height>= result.size()){
			result.add(new LinkedList<>());
		}
		List<Integer> sbuList = result.get(height);
		if (height%2==0){
			sbuList.add(root.val);
		}else {
			sbuList.add(0, root.val);
		}
		travel(result,root.left,height+1);
		travel(result,root.right,height+1);
	}
}
